package DynamicProgramming;

/**
 * 跳跃点法
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/17 12:22
 */
public class GKnapsack {
    public static void main(String[] args) {
        final int number = 5;//物品数
        final int capacity = 10;//背包容量
        final int[] w = {0, 2, 2, 6, 5, 4};            //商品的体积
        final int[] v = {0, 6, 3, 5, 4, 6};            //商品的价值

        int[] item = new int[number + 1];
        int[][] p = knapsack(w, v, capacity);
        item = show(number, w, v, p, PLEN, item);

        for (int i = 0; i < PLEN; i++) {
            System.out.println("(" + p[i][0] + "," + p[i][1] + ") ");
        }
        for (int i = 1; i <= number; i++) {
            System.out.print(item[i]+ " ");
        }
    }


    static int PLEN = 0;// 记录节点数
    static int QLEN = 0;

    /**
     * 获取跳跃点
     * @param w 存放质量列表
     * @param v 存放价值列表
     * @param capacity 背包空间
     * @return 跳跃点集合
     */
    static int[][] knapsack(int[] w, int[] v, int capacity) {
        int[][] p = new int[100][2];//存放跳跃点 重量w:价值v
        p[0][0] = 0;
        p[0][1] = 0;
        PLEN = 1;

        for (int i = 1; i < w.length; i++) {
            int[][] q = new int[16][2];//记录装入当前物品的信息
            QLEN = 0;
            for (int j = 0; j < PLEN; j++) {
                if (w[i] + p[j][0] <= capacity) { // 装的下
                    q[j][0] = w[i] + p[j][0];
                    q[j][1] = v[i] + p[j][1];// 记录
                    QLEN++;
                }
            }
            p = merge(p, q);// 归并
        }


        return p;
    }

    /**
     * 归并跳跃点（清除受控点：w大，但价值小的点。）
     * @param p
     * @param q
     * @return
     */
    static int[][] merge(int[][] p, int[][] q) {
        //从p, q中取出跳跃点
        int lo = 0;
        int[][] o = new int[64][2];

        // 从p中筛选出跳跃点
        for (int j = 0; j < PLEN; j++) {
            int pw = p[j][0];
            int pv = p[j][1];
            boolean flag = true;
            for (int k = 0; k < QLEN; k++) {
                if (pw >= q[k][0] && pv <= q[k][1]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                o[lo][0] = pw;
                o[lo++][1] = pv;
            }

        }
        //从q中筛选跳跃点
        for (int j = 0; j < QLEN; j++) {
            int qw = q[j][0];
            int qv = q[j][1];
            boolean flag = true;
            for (int k = 0; k < PLEN; k++) {
                if (qw >= p[k][0] && qv <= p[k][1]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                o[lo][0] = qw;
                o[lo++][1] = qv;
            }

        }

        PLEN = lo; //记录节点数
        return o;
    }

    /**
     * 构造最优解
     * @param num 正在解析第num物品
     * @param w 存储物品质量
     * @param v 存储物品价值
     * @param p 存储跳跃点
     * @param point 正在解析第point跳跃点
     * @param item 解空间
     * @return 返回解空间
     */
    private static int[] show(int num, int[] w, int[] v, int[][] p,int point, int[] item ) {
        if (num <= 0 || point <= 0) {
            return item;
        }
        int pw = p[point-1][0] - w[num];
        int pv = p[point-1][1] - v[num];
        if (pw < 0 || pv < 0) {
            return show(num - 1, w, v, p, point,item);
        }
        for (int i = point ; i > 0; i--) {
            if (pw == p[i - 1][0] && pv == p[i - 1][1]) {
                item[num] = 1;
                return show(num - 1, w, v, p, i, item);
            }
        }
        return show(num - 1, w, v, p, point,item);
    }

}
